/**
* License apache2.0
*/
package org.mnzd.tree.btree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.function.Supplier;
import java.util.stream.Stream;

/**
 * 流式B-Tree搜索树,可以用来搜索树节点,本数据结构是基于Java8的stream实现的B-Tree数据结构<br/>
 * 流式B-Tree搜索树基于流式(Stream)B-tree的搜索算法，采用后序遍历构造搜索完成后的“结果树”结构<br/>
 * 使用哈希表存储树的路径关键字，并指向B-Tree的各个节点的引用地址，在对B-Tree进行插入、修改、删除时，通过<br/>
 * 路径关键字查找到B-Tree的节点，进行数据更新，搜索性能较好
 * 
 * 本数据结构暂时不提供英文的代码，因为我的英文还不够好, Mnzd是码农知道开源组织的作品<br/>
 * 
 * @author 李声波
 *
 */
public class MnzdTree {

	// 流
	private Supplier<Stream<TreeModel>> stream;
	// 初始化树节点缓存,离散存储所有的树节点关键字，查找节点时速度快
	// 利用JAVA的引用原理，只要在构造树节点时设置了依赖关系，在流中不需要再单独设置树节点的关系
	private ConcurrentMap<String, TreeModel> treeNodeCache = new ConcurrentHashMap<String, TreeModel>();
	// 搜索完成后的树节点
	private TreeModel searchedRoot;
	private StringBuffer treeStreing = new StringBuffer();
	// 存储所有父节点的路径关键字
	private ConcurrentMap<String, TreeModel> parent = new ConcurrentHashMap<String, TreeModel>();
	// 树的高度
	private Integer deep = 0;

	/**
	 * 将一整颗树转换为流<br/>
	 * 该方法基于递归算法 使用前提：已经在内存中构建好一整树<br/>
	 * 为了防止内存溢出，建议转换成流后，自动回收原来的TreeModel<br/>
	 * 
	 * @param root
	 *            根节点
	 */
	public boolean asStream(TreeModel root) {
		try {
			setAllNode(root);
			stream = () -> treeNodeCache.values().stream();
			return true;
		} catch (Exception e) {
			// TODO: handle exception
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * 转换为流
	 * 
	 * @return
	 */
	public void asStream() {
		// 转换为流
		stream = () -> treeNodeCache.values().stream();
	}

	/**
	 * 通过关键字搜索树节点 并重新构建一棵具有父子节点关系的树
	 * 
	 * @param key
	 * @return
	 */
	public TreeModel serachByKey(String key) {
		// 每次搜索之前清空根节点的子节点
		this.searchedRoot = null;
		parent.clear();
		// 构建一颗新的树
		Iterator<TreeModel> it = stream.get().filter(s -> s.getText().contains(key)).iterator();
		while (it.hasNext()) {
			TreeModel treeModel = it.next();
			TreeModel temp = getRootNode(treeModel);
			if (temp != null) {
				this.searchedRoot = temp;
				continue;
			}
		}
		if (this.searchedRoot == null) {
			this.searchedRoot = new TreeModel("0000", "没有查找到相关节点", 0L, false, "");

		}
		return this.searchedRoot;
	}

	/**
	 * 得到根节点 该算法采用后序遍历的方法实现，从搜索到叶节点开始，往上递归查找父节点，直到找到根节点后跳出循环
	 * 
	 * @param leaf
	 * @return
	 */
	private TreeModel getRootNode(TreeModel leaf) {
		// 如果根节点不为空
		if (leaf.getParent() != null) {
			//通过节点的父节点查找路径信息中是否有父节点
			TreeModel oldParentNode = parent.get(leaf.getParent().getPath());
			TreeModel node = (oldParentNode == null ? new TreeModel() : oldParentNode);
			try {
				if (oldParentNode == null) {
					TreeModel tempParent = leaf.getParent();
					node = new TreeModel(tempParent.getId(), tempParent.getText(), tempParent.getParent(),
							tempParent.getChildren(), false, "",tempParent.getPath());
					List<TreeModel> childrens = new ArrayList<TreeModel>();
					childrens.add(leaf);
					node.setChildren(childrens);
				} else {
					setTreeNode(node, leaf);
				}
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			String key = leaf.getParent().getPath();
			if (parent.get(key) == null) {
				parent.put(key, leaf.getParent());
			}
			return getRootNode(node);
		} else {
			String key = leaf.getPath();
			if (parent.get(key) == null) {
				parent.put(key, leaf);
			}
			return leaf;
		}
	}

	/**
	 * 递归设置所有的节点
	 * 
	 * @param list
	 * @param root
	 */
	private void setAllNode(TreeModel root) {
		if (!isList(root.getChildren()))
			return;
		@SuppressWarnings("unchecked")
		List<TreeModel> childs = (List<TreeModel>) root.getChildren();
		for (TreeModel treeModel : childs) {
			treeNodeCache.put(treeModel.getPath(), treeModel);
			if (!isList(root.getChildren()))
				continue;
			setAllNode(treeModel);
		}
	}

	/**
	 * 向已经存在的父节点添加叶节点
	 * 
	 * @param node
	 * @param leaf
	 */
	@SuppressWarnings("unchecked")
	private void setTreeNode(TreeModel node, TreeModel leaf) {
		List<TreeModel> children = null;
		if (node.getChildren() instanceof Boolean) {
			children = new ArrayList<TreeModel>();
		} else {
			children = (List<TreeModel>) node.getChildren();
		}
		// 判断节点是否已经存在
		if (!children.contains(leaf)) {
			if (leaf.getParent() == null) {
				leaf.setParent(node);
			}
			children.add(leaf);
			node.setChildren(children);
		} else {
			if (children.indexOf(leaf) == -1)
				return;
			// 如果存在该节点，则更新
			children.set(children.indexOf(leaf), leaf);
		}

	}

	/**
	 * 判断是否为集合
	 * 
	 * @param children
	 * @return
	 */
	private boolean isList(Object children) {
		if (children != null) {
			if (children instanceof List) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 添加节点 该方法可以在运行期间动态追加节点，适用于新增操作
	 * 
	 * @param node
	 */
	public MnzdTree addTreeNode(TreeModel node) {
		if (node.getPath() == null) {
		}
		TreeModel temp = treeNodeCache.get(node.getPath());
		if (temp != null) {
			temp = node;
		} else {
			
			treeNodeCache.put(node.getPath(), node);
		}
		stream = () -> treeNodeCache.values().stream();
		return this;
	}

	/**
	 * 根据路径添加节点
	 * 
	 * @param path
	 *            当前节点的路径
	 * @param node
	 *            当前节点
	 */
	public MnzdTree addTreeNode(String path, TreeModel node) {
		node.setPath(path);
		// 对String类型的变量进行修改，不用定义新的变量，因为不会改变原有的值
		String parentPath = path.lastIndexOf("/") != -1 ? path.substring(0, path.lastIndexOf("/")) : path;
		TreeModel parentNode = treeNodeCache.get(parentPath);
		if (parentNode != null) {
			setTreeNode(parentNode, node);
		}
		this.treeNodeCache.put(path, node);
		stream = () -> treeNodeCache.values().stream();
		return this;
	}

	/**
	 * 通过父路径添加子节点
	 * 
	 * @param parentPath
	 *            在父路径添加节点
	 * @param node
	 *            当前节点
	 */
	public MnzdTree addTreeNodeOnParent(String parentPath, TreeModel node) {
		// 用ID和父路径作为当前路径
		node.setPath(parentPath + "/" + node.getId());
		TreeModel parentNode = treeNodeCache.get(parentPath);
		if (parentNode != null) {
			setTreeNode(parentNode, node);
		}
		this.treeNodeCache.put(node.getPath(), node);
		stream = () -> treeNodeCache.values().stream();
		return this;
	}

	/**
	 * 删除元素
	 * 
	 * @param path
	 *            树节点的路径
	 */
	public MnzdTree removeTreeNode(String path) {
		String key = path;
		TreeModel treeModel = treeNodeCache.get(key);
		if (treeModel == null) {
			return this;
		}
		if (treeModel.getParent() != null) {
			if (treeModel.getParent().getChildren() instanceof List) {
				@SuppressWarnings("unchecked")
				List<TreeModel> children = (List<TreeModel>) treeModel.getParent().getChildren();
				children.remove(treeModel);
			}
			if (treeModel.getChildren() instanceof List) {
				@SuppressWarnings("unchecked")
				List<TreeModel> children = (List<TreeModel>) treeModel.getChildren();
				children.forEach(node -> {
					treeNodeCache.remove(node.getPath(), node);
				});
				children.clear();
			}
		} else {
			if (treeModel.getChildren() instanceof List) {
				@SuppressWarnings("unchecked")
				List<TreeModel> children = (List<TreeModel>) treeModel.getChildren();
				children.clear();
				treeNodeCache.clear();
			}
		}

		treeNodeCache.remove(key, treeModel);
		this.parent.remove(key, this.parent.get(key));
		stream = () -> treeNodeCache.values().stream();
		return this;
	}
	
	/**
	 * 通过路径关键字删除节点
	 * @param key
	 * @return
	 */
	public MnzdTree removeTreeNodeByKey(String key)
	{
		stream.get().filter(s->s.getId().equals(key)).forEachOrdered(node->{
			removeTreeNode(node.getPath());
		});
		return this;
	}

	/**
	 * 移动节点
	 * 
	 * @param origPath
	 *            源节点的路径
	 * @param targetPath
	 *            目标节点的路径
	 */
	public void moveTreeNode(String origPath, String targetPath) {
		TreeModel orig = treeNodeCache.get(origPath);
		TreeModel target = treeNodeCache.get(targetPath);
		if (orig != null) {
			setTreeNode(target, orig);
			// 删除原来的节点
			deleteTreeNodeByPath(origPath, orig);
			// 更新路径
			orig.setPath(target.getPath());
			treeNodeCache.put(orig.getPath(), orig);
		}
		stream = () -> treeNodeCache.values().stream();
	}

	/**
	 * 通过路径删除指定节点，并删除指定节点下的子节点 并删
	 * 
	 * @param path
	 */
	private void deleteTreeNodeByPath(String path, TreeModel orig) {
		// 重新设置关键路径
		treeNodeCache.remove(path, orig);
		if (isList(orig.getChildren())) {
			List<TreeModel> treeModel = convertList(orig);
			treeModel.remove(orig);
		}
	}

	/**
	 * 修改对象
	 * 
	 * @param origPath
	 *            源节点路径
	 * @param targetPath
	 *            目标节点路径
	 * @param newNode
	 *            新的节点
	 */
	public void updateTreeNode(String origPath, String targetPath, TreeModel newNode) {
		TreeModel orig = treeNodeCache.get(origPath);
		TreeModel target = treeNodeCache.get(targetPath);
		if (orig != null && target != null) {
			// 删除掉原有的路径关键字
			deleteTreeNodeByPath(origPath, orig);
			// 将新的值赋给旧的节点
			// 注意一定不要改变内存地址，也就是不能用新的TreeModel变量，否则将导致树节点关系错乱
			orig.setId(newNode.getId());
			orig.setText(newNode.getText());
			// orig.setChildren(newNode.getChildren());
			// orig.setParent(newNode.getParent());
			orig.setPath(targetPath);
			setTreeNode(target, orig);
			// 重新设置新的路径关键字
			treeNodeCache.put(orig.getPath(), orig);
			
		} else if (orig != null) {
			// 删除掉原有的路径关键字
			deleteTreeNodeByPath(origPath, orig);
			// 将新的值赋给旧的节点
			// 注意一定不要改变内存地址，也就是不能用新的TreeModel变量，否则将导致树节点关系错乱
			orig.setId(newNode.getId());
			orig.setText(newNode.getText());
			// orig.setChildren(newNode.getChildren());
			// orig.setParent(newNode.getParent());
			orig.setPath(targetPath);
			treeNodeCache.put(orig.getPath(), orig);
		}
		stream = () -> treeNodeCache.values().stream();
	}

	/**
	 * 得到流
	 * 
	 * @return
	 */
	public Stream<TreeModel> stream() {
		return this.stream.get();
	}

	/**
	 * 遍历树节点
	 * 
	 * @return
	 */
	public String forEachTree() {
		treeStreing.append(this.searchedRoot.getText() + "\r");
		subForEachTree(this.searchedRoot);
		return treeStreing.toString();
	}

	/**
	 * 递归查找树的节点
	 * 
	 * @param node
	 */
	private void subForEachTree(TreeModel node) {
		if (!isList(node.getChildren())) {
			treeStreing.append("  |_");
			treeStreing.append(node.getText());
			return;
		}
		@SuppressWarnings("unchecked")
		List<TreeModel> children = (List<TreeModel>) (node == null ? this.searchedRoot.getChildren()
				: node.getChildren());
		for (int i = 0; i < children.size(); i++) {
			TreeModel treeModel = children.get(i);
			for (int j = 0; j <= deep; j++) {
				treeStreing.append("  |_");
			}
			treeStreing.append(treeModel.getText()).append("\r");
			if (isList(treeModel.getChildren())) {
				++deep;
				subForEachTree(treeModel);
			}
			if (i == children.size() - 1) {
				--deep;
			}
		}
	}

	/**
	 * 返回搜索后的树节点
	 */
	@Override
	public String toString() {
		if (this.searchedRoot != null) {
			return forEachTree();
		}
		return "empty";
	}

	/**
	 * 转换为List
	 * 
	 * @param orig
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private List<TreeModel> convertList(TreeModel orig) {
		List<TreeModel> list = (List<TreeModel>) orig.getChildren();
		return list;
	}
}
